A mutual exclusion protocol may be generally defined a protocol in which a process can gain the right to execute for a fixed time interval without interference from other processes. Mutual exclusion may be required whenever processes need to gain access to “shared resources,” such as code, data or memory in file systems and databases. However, a plurality of processes trying to gain access to a critical section of memory or code at the same time may lead to various problems, such as data corruption. Certain processes should be forced to execute a critical section or shared resource separately and serially, as opposed to concurrently. In order to achieve this goal, a mutual exclusion protocol may be required and enforced.
One mutual exclusion protocol used is a “Maekawa” type protocol. In this class of protocols, a process pi requests permission to enter the critical section from a set Qi of processes, such that Qi∩Qj≠Ø for all i, j. Each process in a request set Qi grants exclusive access to the critical section until it is exited, and Pi is allowed to enter the critical section only if all processes in Qi grant Pi access. Due to the intersection property of request sets and exclusive locking at each process in a request set, only one process can be in the critical section at any time.
Due to these above properties, however, Maekawa-type algorithms are also generally prone to “deadlock” and consequently require extra messages to detect and recover from deadlocks. A “deadlock” is generally defined to occur when a process or processes become stuck, because some process has not disengaged itself from a critical section of the code for an indefinite period. Deadlock-free Maekawa-type protocols have been proposed by strengthening the constraints on request sets so that for all i, j, either piεQj or Pj εQi. However, this strengthening may not be possible if clients (i.e. a first process) requesting mutual exclusion are distinct from servers (i.e. a second process) that comprise the request sets. Clients cannot be added to request sets because they are transient and because the population of clients that might contend is not known a priori.
One subclass of mutual exclusion protocols is what is known as a “backoff” protocol. In one embodiment of a backoff protocol, if the backoff protocol detects that a sent message somehow collides with another process, the backoff protocol “backs off” for a random delay and tries again later. Backoff protocols have been used to achieve mutual exclusion to multiple access channels, such as Ethernet. The collision detection protocol of Ethernet is a well-known example of one embodiment of a backoff protocol.
The performance of a mutual exclusion protocol, such as a backoff protocol, can generally be characterized in terms of an “amortized system response time”. The amortized system response time may be generally defined as the mean delay that each of t processes incurs before entering the shared resource, the critical section, assuming that all t (and no others) start contending at the same time.
Other distributed mutual exclusion protocols can be derived from a mutual exclusion protocol for shared-memory multi-processors, by simply emulating each shared variable used in the protocol with a distributed implementation. (For more background in this area, please see “Secure and scalable replication in Phalanx” by D. Malkhi and M. K. Reiter, in Proceedings of the 17th IEEE Symposium on Reliable Distributed Systems, October, 1998, which is hereby incorporated by reference in its entirety). While the resulting algorithm may have superior amortized system response time (asymptotically), the performance of this protocol could be unacceptable, such as in a context of contention-free performance, perhaps due to the overhead of the variable emulation protocols. This unacceptable performance also holds for the backoff-style mutual exclusion algorithms explored above in the shared-memory setting. One such example is “The performance of spin-lock alternatives for shared-memory multiprocessors” by T. E. Anderson, in IEEE Transactions on Parallel and Distributed Systems, January 1990, (hereby incorporated by reference in its entirety) which assumes even stronger objects than shared variables.
Distributed mutual exclusion protocols in asynchronous environment have been disclosed in the context of the employment of “consensus” in the timed asynchronous model, such as disclosed in “On the possibility of consensus in asynchronous systems” by C. Fetzer and F. Cristian in Proceedings of the 1995 Pacific Rim International Symposium on Fault-Tolerant Systems, December, 1995, which is hereby incorporated by reference in its entirety. Consensus may be generally defined as a distributed protocol by which each process proposes a value and then decides on a value, and so that every process that does not fails decides the same value. The works of Lamport on Paxos (“The Part-time parliament” by L. Lamort, in ACM Transactions on Computer Science, May 1998, which is hereby incorporate by reference in its entirety), and of Keidar and Dolev who disclose an extended 3-phase commit (E3PC) protocol in “Increasing the resilience of distributed and replicated database systems” by I. Keidar and D Dolev, which is also hereby incorporated by reference in its entirety. The 3-phase commit is a well-known protocol for committing an update to a replicated database so that no two replicas commit a different update. These above works compose and disclose a mutual exclusion protocol with a “commit” protocol to derive solutions.
Paxos and E3PC, while building on mutual exclusion protocols, do not propose mutual exclusion implementations of their own. Fetzer and Cristian employ a mutual exclusion protocol that rotates the preference for access to the critical section among the possible process contenders in sequence, but enables the next preferred contender to be bypassed without delay if that contender is unavailable. In order to achieve this, however, the protocol relies on clock synchronization among the participating processes.
Therefore, what is needed in the art is an efficient mutual exclusion primitive that overcomes the deficiencies of the prior art, and by admitting arbitrary (Byzantine) server failures in the ordering protocol.